import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param root TreeNode类 
     * @param o1 int整型 
     * @param o2 int整型 
     * @return int整型
     */

    public int dfs(TreeNode node, ArrayList<Integer> arr, int target) {
        if (node == null)
            return 0;
        
        if (node.val == target || dfs(node.left, arr, target) == 1 || dfs(node.right, arr, target) == 1) {
            arr.add(node.val);
            return 1;
        }

        return 0;
    }

    public TreeNode helper (TreeNode node, int o1, int o2) {
        if (node == null || node.val == o1 || node.val == o2)
            return node;
        
        TreeNode left = helper(node.left, o1, o2);
        TreeNode right = helper(node.right, o1, o2);

        if (left == null)
            return right;
        if (right == null)
            return left;
        
        return node;
    }

    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        // write code here
        // zxy
        /*
        ArrayList<Integer> arr1 = new ArrayList<>();
        ArrayList<Integer> arr2 = new ArrayList<>();

        dfs(root, arr1 ,o1);
        dfs(root, arr2, o2);

        int ret = -1;
        for (int i = arr1.size() - 1, j = arr2.size() - 1; i >= 0 && j >= 0; i -= 1, j -= 1) {
            if (arr1.get(i).intValue() == arr2.get(j).intValue())
                ret = arr1.get(i);
            else
                break;
        }

        return ret;
        */

        // 递归
        return helper(root, o1, o2).val;
    }
}

/*
    public int lowestCommonAncestor(TreeNode root, int o1, int o2) {
        //记录遍历到的每个节点的父节点。
        Map<Integer, Integer> parent = new HashMap<>();
        Queue<TreeNode> queue = new LinkedList<>();
        parent.put(root.val, Integer.MIN_VALUE);//根节点没有父节点，给他默认一个值
        queue.add(root);
        //直到两个节点都找到为止。
        while (!parent.containsKey(o1) || !parent.containsKey(o2)) {
            //队列是一边进一边出，这里poll方法是出队，
            TreeNode node = queue.poll();
            if (node.left != null) {
                //左子节点不为空，记录下他的父节点
                parent.put(node.left.val, node.val);
                //左子节点不为空，把它加入到队列中
                queue.add(node.left);
            }
            //右节点同上
            if (node.right != null) {
                parent.put(node.right.val, node.val);
                queue.add(node.right);
            }
        }
        Set<Integer> ancestors = new HashSet<>();
        //记录下o1和他的祖先节点，从o1节点开始一直到根节点。
        while (parent.containsKey(o1)) {
            ancestors.add(o1);
            o1 = parent.get(o1);
        }
        //查看o1和他的祖先节点是否包含o2节点，如果不包含再看是否包含o2的父节点……
        while (!ancestors.contains(o2))
            o2 = parent.get(o2);
        return o2;
    }
*/